The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. EP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). The use of programmable software or firmware have advantages as they provide some level of flexibility, which becomes especially important as new protocols and services are added to existing network. Customer typically desire to use their existing hardware (e.g., routers, switches etc.) to support these new protocols and services. However, known software and firmware implementations are relatively slow, and typically place a performance bound which may be incompatible with new requirements. Various applications that use packet classification, such as Security Access Control, Quality of Service etc., typically need to perform many matches on source and destination port numbers, protocol and/or other header fields, etc. in order to identify a corresponding netflow.
A known approach of identifying traffic flows for the purpose of prioritizing packets uses CAMs to identify and “remember” traffic flows allowing a network switch or router to identify packets belonging to that flow, at wire speed, without processor intervention. In one approach, learning new flows is automatic. Once a flow is identified, the system software assigns the proper priority to the newly identified flow. In each of the cases where learning is necessary (i.e., adding a new connection), the next free address of the device is read out so the system software can keep track of where the new additions are being placed. This way, the system software can efficiently remove these entries when they are no longer active. If aging is not used, the system software would need to keep track of the locations of every entry, and when a session ends, remove the corresponding entries. This is not a real-time issue, so software can provide adequate performance. Additionally, it is possible, even desirable to store timestamp information in the device to facilitate aging and purging of inactive flow identifiers.
For a purpose and context different from prioritizing packets, it is desirable to collect statistics about traffic flows (also referred to as “netflows”). These statistics can provide the metering base for real-time and post-processing applications including network traffic accounting, usage-based network billing, network planning, network monitoring, outbound marketing, and data mining capabilities for both service provider and enterprise customers.
However, known implementations for collecting netflow statistics use a CPU to examine each packet and a hashing function typically accessing a large data structure to identify a netflow and to maintain corresponding statistics. Such an implementation is CPU intensive, and may not be able to operate at the higher packet rates of certain systems. Needed are new methods and apparatus for collecting statistics on netflows.